package com.lyt.springboot.util.algorithm;

import java.util.HashMap;
import java.util.Map;

public class S19 {
    /*
    给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        if(numbers==null || numbers.length ==0) {
            return 0;
        }
        HashMap<Integer,Integer> hash = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if(!hash.containsKey(numbers[i])) {
                hash.put(numbers[i],1);
            }else {
                hash.put(numbers[i],hash.get(numbers[i])+1);
            }

        }
        int len = numbers.length/2;
//        for (int i = 0; i <hash.size() ; i++) {
//            if(hash.get(i)>len) {
//                return i;
//
//            }
//
//        }
        for(Integer key:hash.keySet()) {
            if(hash.get(key)>len) {
                return key;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(1,2);
        map.put(2,3);
        map.put(4,5);
        for (int i = 0; i < map.size(); i++) {
            System.out.println(map.get(i));

        }
    }

}
